package dataStructure.study.array;

/**
 * Author: shangsf
 * Date: 2021/3/22 22:00
 * Description: 动态扩容数组
 */
public class DynamicArray {

    private static final int DEFAULT_CAPACITY=10;

    private static final int MAX_CAPACITY=Integer.MAX_VALUE-8;

    private static final Object [] DEFAULT_EMPTY_DATA={};

    private Object [] elementData;

    private int size;

    public DynamicArray(){
        elementData=DEFAULT_EMPTY_DATA;
        size=0;
    }

    public void add(int index,Object element){
        checkRange(index);
        resize(size+1);
        //复制数据
        for(int i=size;i>index;i--){
            elementData[i]=elementData[i-1];
        }
        elementData[index]=element;
        size++;
    }

    public Object set(int index,Object element){
        checkRange(index);
        Object old=elementData[index];
        elementData[index]=element;
        return old;
    }

    public Object get(int index){
        checkRange(index);
        return elementData[index];
    }

    public void add(Object element){
        resize(size+1);
        elementData[size++]=element;
    }

    public void remove(int index){
        checkRange(index);

        if(index==size-1){
            elementData[index]=null;
        }else {
            for (int i=index;i<size-1;i++){
                elementData[i]=elementData[i+1];
            }
            elementData[--size]=null;
        }
    }

    public int size(){
        return size;
    }

    void resize(int minCapacity){
        if(elementData==DEFAULT_EMPTY_DATA){
            minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);
        }
        if(minCapacity>elementData.length){
            //扩张到1.5倍
            int newCapacity=elementData.length+elementData.length>>1;
            if(newCapacity<minCapacity){
                newCapacity=minCapacity;
            }
            if(newCapacity>MAX_CAPACITY){
                newCapacity=Integer.MAX_VALUE;
            }
            //复制一个新的数组
            Object [] newElementData=new Object[newCapacity];
            for(int i=0;i<elementData.length;i++){
                newElementData[i]=elementData[i];
            }
            elementData=newElementData;
        }
    }

    void checkRange(int index){
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
        }
    }
}
